226. 翻转二叉树

Similar Question

leading to the advanced question

Solution Tips

方案一: 递归

var invertTree = function(node) {
    // 从底部开始翻转, 先反转最底层的节点, 所以肯定是一个后序遍历
    if (node === null) return null;
    if (node.left === null && node.right === null) return node;

    invertTree(node.left);
    invertTree(node.right);
    // 翻转
    [node.left, node.right] = [node.right, node.left];
    return node;

    // 迭代法也是一样做的, 就是利用数组做元素的交换而已, 利用栈做反转是最常见的思路
    // 先序遍历 push, 再次先序遍历 pop 出来就好了
};

方案二: 迭代

  var invertTree = function(root) {
    if(root==null) return null
    const stack = [root]
    while(stack.length>0){
      const cur = stack.pop()
      let left = cur.left,
          right = cur.right
      cur.left = right
      cur.right = left
      if(cur.left) stack.push(cur.left)
      if(cur.right) stack.push(cur.right)
    }
    return root
  }